import java.util.Arrays;

/**
 * @Description: test
 * @Author Stark
 * @Date 2022/3/28 18:50
 **/
public class Test {
    //插入排序
    public static void insertSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i; j >= 0; j--) {
                if(arr[j] > arr[j + 1]){
                    swap(arr,j,j + 1);
                }
            }
        }
    }

    private static void swap(int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
    //反转链表
    public static void reverse(Node head){

    }

    //求二叉树高度
    public static int height(TreeNode head){
        if(head == null){
            return 0;
        }
        return Math.max(height(head.left),height(head.right)) + 1;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3,2,5,8,4,7,6,9};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(10);
        TreeNode node6 = new TreeNode(10);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        node4.left = node6;
        System.out.println(height(node1));
    }
}
class Node{
    private int val;
    private Node next;

    public Node(int val) {
        this.val = val;
    }
}

class TreeNode{
    private int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
